import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.combinationSum(new int[]{2,3,6,7}, 7));
        System.out.println(s.combinationSum(new int[]{2,3,5}, 8));
        System.out.println(s.combinationSum(new int[]{2}, 1));
    }
}


class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        findCombinationSum(candidates, candidates.length - 1, target, ans, new LinkedList<Integer>());
        return ans;
    }

    void findCombinationSum(int[] candidates, int maxIdx, int target, List<List<Integer>> ans, LinkedList<Integer> cur){
        if(target == 0){
            ans.add(new ArrayList<>(cur));
            return;
        }

        for(int i = maxIdx; i >= 0; i--){
            if(target >= candidates[i]){
                cur.add(candidates[i]);
                findCombinationSum(candidates, i, target - candidates[i], ans, cur);
                cur.removeLast();
            }
        }
    }
}